package com.huawei.tree;

import com.huawei.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author admin
 * @Description 129.求根节点到叶子节点数字总和
 * @Date 2023/11/16/22:55
 * @Version 1.0
 */
public class SumNumbers {

	int res = 0;
	List<Integer> list = new ArrayList<>();  // 记录每一条到叶子结点的路径上所有的节点

	public int sumNumbers(TreeNode root) {
		dfs(root);
		return res;
	}

	private void dfs(TreeNode root) {
		// 循环终止条件
		if (root == null) {
			return;
		}
		// 加入路径上的每一个节点
		list.add(root.val);
		// 为叶子结点时，加入总和中
		if (root.left == null && root.right == null) {
			res = res + sum(new ArrayList<>(list));
		}
		// 递归遍历左子树和右子树
		dfs(root.left);
		dfs(root.right);
		// 回溯
		list.remove(list.size() - 1);

	}

	// 每一条到叶子结点的路径上所有节点之和
	private int sum(List<Integer> list) {
		int s = 0;
		for (Integer num : list) {
			s = s * 10 + num;
		}
		return s;
	}

}
